class Solution
{
public:
    bool isValid(string s)
    {
        stack<char> st;
        for (char c : s)
        {
            switch (c)
            {
            case '(':
            case '[':
            case '{':
            {
                st.push(c);
                break;
            }
            case ')':
            case ']':
            case '}':
            {
                if (st.empty())
                {
                    return false;
                }
                if (isPair(st.top(), c))
                {
                    st.pop();
                }
                else
                {
                    return false;
                }
                break;
            }
            default:
            {
                return false;
            }
            }
        }
        return st.empty();
    }

private:
    bool isPair(char left, char right)
    {
        switch (left)
        {
        case '(':
            return right == ')';
        case '[':
            return right == ']';
        case '{':
            return right == '}';
        }
        return false;
    }
};